This video provides an introductory lecture to Binary Heap.
This track of the course covers the topic "Heap".
In details, this track will cover:
Objective: The objective of this track is to familiarize the learners with Heaps.
Track Content:
Assessment: All Tracks in every week are associated with weekly contests.
This video provides an introductory lecture to Binary Heap.
This video discusses the implementation of a Binary Heap.
Codes:
This video implements the insertion method of Binary Heap.
Codes:
This video discusses the Heapify and Extract operation and how can it be implemented in a Binary Heap.
Codes:
This video discusses the Decrease Key, Delete and Build Heap operation of Binary Heap.
Codes:
Working of Heap Sort with implementation.
Codes:
This video discusses the working and implementation of the Priority Queue in C++. It also discusses the various general applications of Priority Queue.
Codes:
This video explains the implementation of the Priority Queue in Java.
Codes:
This video discusses the problem of how to Sort an array that is already k-sorted.
Codes:
This video discusses the problem of buying the maximum items with a given sum.
Codes:
This video discusses the problem of calculating the K Largest Elements in an unsorted array
Codes:
This video discusses the problem of how to Merge K Sorted Arrays.
Codes:
This video discusses the calculation of a Median of a Stream.
Codes:

Representing Binary Heaps
Since a Binary Heap is a complete Binary Tree, it can be easily represented using Arrays.| Arr[(i-1)/2] | Returns the parent node |
| Arr[(2*i)+1] | Returns the left child node |
| Arr[(2*i)+2] | Returns the right child node |
Heapifying an Element
Generally, on inserting a new element onto a Heap, it does not satisfy the property of Heap as stated above on its own. The process of placing the element at the correct location so that it satisfies the Heap property is known as Heapify.


Given a Binary Heap and an element present in the given Heap. The task is to delete an element from this Heap.
Suppose the Heap is a Max-Heap as:
The element to be deleted is root, i.e. 10.
Process:
The last element is 4.
Step 1: Replace the last element with root, and delete it.
Step 2: Heapify root.
Final Heap:![]()
5 4 3 2
Let us try deleting 30 from below Min Heap
We replace 30 with -INF
We move -INF to root by swapping with parent
nodes one by one
Now Delete Root (We first replace it with last node
then call heapify)![]()
Given a Binary Heap and a new element to be added to this Heap. The task is to insert the new element to the Heap maintaining the properties of Heap.
Suppose the Heap is a Max-Heap as:
The new element to be inserted is 15.
Process:
Step 1: Insert the new element at the end.
Step 2: Heapify the new element following bottom-up
approach.
-> 15 is less than its parent 3, swap them.
-> 15 is again less than its parent 10, swap them.
Therefore, the final heap after insertion is:
-> 15 is less than its parent 3, swap them.
15 5 10 2 4 3
Given N elements. The task is to build a Binary Heap from the given array. The heap can be either Max Heap or Min Heap.
Root is at index 0 in array.
Left child of i-th node is at (2*i + 1)th index.
Left child of i-th node is at (2*i + 2)th index.
Parent of i-th node is at (i-1)/2 index.
Last non-leaf node = parent of last-node.
or, Last non-leaf node = parent of node at (n-1)th index.
or, Last non-leaf node = Node at index ((n-1) - 1)/2.
= (n - 2)/2.
Array = {1, 3, 5, 4, 6, 13, 10, 9, 8, 15, 17}
Corresponding Complete Binary Tree is:

The task to build a Max-Heap from above array.
Total Nodes = 11.
Last Non-leaf node index = (11/2) - 1 = 4.
Therefore, last non-leaf node = 6.
To build the heap, heapify only the nodes:
[1, 3, 5, 4, 6] in reverse order.
Heapify 6: Swap 6 and 17.

Heapify 4: Swap 4 and 9.

Heapify 5: Swap 13 and 5.

Heapify 3: First Swap 3 and 17, again swap 3 and 15.

Heapify 1: First Swap 1 and 17, again swap 1 and 15,
finally swap 1 and 6.

Array representation of Heap is:
17 15 13 9 6 5 10 4 8 3 1
priority_queue< type_of_data > name_of_heap;
priority_queue< type, vector<type>, greater<type> > name_of_heap;
Element at top of Max Heap at every step:
30 20 10 5 1
Element at top of Min Heap at every step:
1 5 10 20 30
Queue<Integer> max_heap = new PriorityQueue<>(
Collections.reverseOrder());
Queue<Integer> min_heap = new PriorityQueue<>();
Some error occured or ide is down,please try again
// To heapify a subtree rooted with node i which is
// an index in arr[]. n is size of heap
void heapify( arr[], n, i)
{
largest = i // Initialize largest as root
l = 2*i + 1 // left = 2*i + 1
r = 2*i + 2 // right = 2*i + 2
// If left child is larger than root
if (l < n && arr[l] > arr[largest])
largest = l
// If right child is larger than largest so far
if (r < n && arr[r] > arr[largest])
largest = r
// If largest is not root
if (largest != i)
{
swap(arr[i], arr[largest])
// Recursively heapify the affected sub-tree
heapify(arr, n, largest)
}
}
// main function to do heap sort
void heapSort( arr[], n)
{
// Build heap (rearrange array)
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i)
// One by one extract an element from heap
for (int i=n-1; i>=0; i--)
{
// Move current root to end
swap(arr[0], arr[i])
// call max heapify on the reduced heap
heapify(arr, i, 0)
}
}
void MinHeap( a[], size)
{
heap_size = size
harr = a // store address of array
int i = (heap_size - 1)/2
while (i >= 0)
{
MinHeapify(i)
i--
}
}
// Method to remove minimum element (or root) from min heap
int extractMin()
{
if (heap_size == 0)
return INT_MAX
// Store the minimum vakue.
int root = harr[0]
// If there are more than 1 items, move the last item to root
// and call heapify.
if (heap_size > 1)
{
harr[0] = harr[heap_size-1]
MinHeapify(0)
}
heap_size--
return root
}
// A recursive method to heapify a subtree with root at given index
// This method assumes that the subtrees are already heapified
void MinHeapify(int i)
{
int l = left(i)
int r = right(i)
int smallest = i;
if (l < heap_size && harr[l] < harr[i])
smallest = l
if (r < heap_size && harr[r] < harr[smallest])
smallest = r
if (smallest != i)
{
swap(& harr[i], & harr[smallest])
MinHeapify(smallest)
}
}
// Returns Minimum Element
int getMin()
{
return harr[0]
}
// Function to return k'th smallest element in a given array
int kthSmallest( arr[], n, k)
{
// Build a heap of n elements: O(n) time
MinHeap(arr, n)
// Do extract min (k-1) times
for (int i=0; i < k-1; i++)
extractMin()
// Return root
return getMin()
}
What is Median?
Median can be defined as the element in the data set which separates the higher half of the data sample from the lower half. In other words we can get the median element as, when the input size is odd, we take the middle element of sorted data. If the input size is even, we pick average of middle two elements in sorted stream.Input: 5 10 15Explanation: Given the input stream as an array of integers [5,10,15]. We will now read integers one by one and print the median correspondingly. So, after reading first element 5, the median is 5. After reading 10,median is 7.5 After reading 15 ,median is 10.
Output: 5
7.5
10
// function to calculate median of streamTime Complexity: O(n Log n)
void printMedian(double arr[], int n)
{
// max heap to store the smaller half elements
priority_queues;
// min heap to store the greater half elements
priority_queue,greater > g;
double med = arr[0];
s.push(arr[0]);
print(med)
// reading elements of stream one by one
/* At any time we try to make heaps balanced and
their sizes differ by at-most 1. If heaps are
balanced,then we declare median as average of
min_heap_right.top() and max_heap_left.top()
If heaps are unbalanced,then median is defined
as the top element of heap of larger size */
for (int i=1; i < n; i++)
{
double x = arr[i];
// case1(left side heap has more elements)
if (s.size() > g.size())
{
if (x < med)
{
g.push(s.top());
s.pop();
s.push(x);
}
else
g.push(x);
med = (s.top() + g.top())/2.0;
}
// case2(both heaps are balanced)
else if (s.size()==g.size())
{
if (x < med)
{
s.push(x);
med = (double)s.top();
}
else
{
g.push(x);
med = (double)g.top();
}
}
// case3(right side heap has more elements)
else
{
if (x > med)
{
s.push(g.top());
g.pop();
g.push(x);
}
else
s.push(x);
med = (s.top() + g.top())/2.0;
}
print(med)
}
}
Asked In: Cisco
Asked In: Amazon
Asked In: Amazon
A | 1, 3, 5, 6, 8, 9 |
B | 9, 6, 3, 1, 8, 5 |
C | 9, 3, 6, 8, 5, 1 |
D | 9, 5, 6, 8, 3, 1 |